package leetcode_zh

import (
	"container/heap"
	"math"
	"math/rand"
	"sort"
	"strconv"
	"strings"
)

/**
 * @Description: 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
 * @Keyword: 如果正整数 i 是一个偶数，那么 i 相当于将 i/2 左移一位的结果，因此偶数 i 和 i/2 的二进制形式 1 的个数是一样的
			如果 i 是奇数，那么 i 相当于将 i/2 左移一位之后再将最右边的位设为 1 的结果，
			因此奇数 i 比 i/2 的二进制形式 1 的个数多 1 个 可以利用这个规律有如下代码
 * @Author: kami
 * @Date: 2022/7/14 18:36
 **/
func countBits003(n int) []int {
	if n == 0 {
		return []int{0}
	}
	var res = make([]int, n+1)
	res[0] = 0
	for i := 1; i <= n; i++ {
		res[i] = res[i>>1] + i&1
	}
	return res
}

/**
 * @Description: 剑指 Offer II 002. 二进制加法 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/14 18:55
 **/
func addBinary(a string, b string) string {
	var res []byte
	var aIdx = len(a) - 1
	var bIdx = len(b) - 1
	var take uint8
	var oo = uint8('0' + '0')
	for aIdx > -1 || bIdx > -1 {
		if aIdx > -1 && bIdx > -1 {
			var sum = a[aIdx] + b[bIdx] - oo + take
			if sum == 0 {
				res = append(res, '0')
			} else if sum == 1 {
				res = append(res, '1')
				take = 0
			} else if sum == 2 {
				res = append(res, '0')
				take = 1
			} else {
				res = append(res, '1')
			}
			aIdx--
			bIdx--
		} else if aIdx > -1 {
			var sum = a[aIdx] - '0' + take
			if sum == 0 {
				res = append(res, '0')
			} else if sum == 1 {
				res = append(res, '1')
				take = 0
			} else {
				res = append(res, '0')
				take = 1
			}
			aIdx--
		} else {
			var sum = b[bIdx] - '0' + take
			if sum == 0 {
				res = append(res, '0')
			} else if sum == 1 {
				res = append(res, '1')
				take = 0
			} else {
				res = append(res, '0')
				take = 1
			}
			bIdx--
		}
	}
	if take > 0 {
		res = append(res, '1')
	}
	// 翻转
	var half = len(res) / 2
	for i := 0; i < half; i++ {
		res[i], res[len(res)-i-1] = res[len(res)-i-1], res[i]
	}
	return string(res)
}

/**
 * @Description: 剑指 Offer II 006. 排序数组中两个数字之和
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/14 22:00
 **/
func twoSum006(numbers []int, target int) []int {
	var left = 0
	var right = len(numbers) - 1
	for left < right {
		var sum = numbers[left] + numbers[right]
		if sum == target {
			return []int{left, right}
		} else if sum > target {
			right--
		} else {
			left++
		}
	}
	return []int{}
}

/**
 * @Description: 剑指 Offer II 088. 爬楼梯的最少成本 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/14 22:10
 **/
func minCostClimbingStairs(cost []int) int {
	var dp = make([]int, len(cost))
	dp[0] = cost[0]
	dp[1] = cost[1]
	for i := 2; i < len(cost); i++ {
		var twoStep = dp[i-2] + cost[i]
		var oneStep = dp[i-1] + cost[i]
		if twoStep < oneStep {
			dp[i] = twoStep
		} else {
			dp[i] = oneStep
		}
	}
	if dp[len(cost)-1] > dp[len(cost)-2] {
		return dp[len(cost)-2]
	}
	return dp[len(cost)-1]
}

/**
 * @Description: 剑指 Offer II 012. 左右两边子数组的和相等 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/15 9:05
 **/
func pivotIndex(nums []int) int {
	var sum = nums[0]
	var preSum = make([]int, len(nums))

	for i := 1; i < len(nums); i++ {
		preSum[i] = preSum[i-1] + nums[i-1]
		sum += nums[i]
	}
	for i := 0; i < len(nums); i++ {
		if sum-preSum[i]-nums[i] == preSum[i] {
			return i
		}
	}
	return -1
}

/**
 * @Description: 剑指 Offer II 018. 有效的回文 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/15 9:22
 **/
func isPalindrome018(s string) bool {
	var left int
	var right = len(s) - 1
	s = strings.ToUpper(s)
	for left < right {
		if s[left] == s[right] {
			left++
			right--
			continue
		}
		if !isDigitOrLetter(s[left]) {
			left++
			continue
		}
		if !isDigitOrLetter(s[right]) {
			right--
			continue
		}
		return false
	}
	return true
}
func isDigitOrLetter(s byte) bool {
	return (s >= '0' && s <= '9') || (s >= 'a' && s <= 'z') || (s >= 'A' && s <= 'Z')
}

/**
 * @Description: 剑指 Offer II 019. 最多删除一个字符得到回文 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/15 10:50
 **/
func validPalindrome(s string) bool {
	var dfs func(left, right int, hasRemoved bool) bool
	dfs = func(left, right int, hasRemoved bool) bool {
		for left < right {
			if s[left] != s[right] {
				if hasRemoved {
					return false
				}
				return dfs(left+1, right, true) || dfs(left, right-1, true)
			}
			left++
			right--
		}
		return true
	}
	return dfs(0, len(s)-1, false)
}

/**
 * @Description: 剑指 Offer II 023. 两个链表的第一个重合节点 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/15 11:01
 **/
func getIntersectionNode023(headA, headB *ListNode) *ListNode {
	var aTurned bool
	var bTruned bool
	var a = headA
	var b = headB
	for a != b {
		if a.Next == nil {
			if aTurned {
				return nil
			}
			a = headB
			aTurned = true
		} else {
			a = a.Next
		}

		if b.Next == nil {
			if bTruned {
				return nil
			}
			b = headA
			bTruned = true
		} else {
			b = b.Next
		}
	}
	return a
}

/**
 * @Description: 剑指 Offer II 024. 反转链表 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/15 11:09
 **/
func reverseList024(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var cur = head
	var pre *ListNode

	for cur.Next != nil {
		var next = cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	cur.Next = pre

	return cur
}

/**
 * @Description: 剑指 Offer II 027. 回文链表
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/15 11:33
 **/
func isPalindrome027(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	mid := getMiddle(head)
	l := head
	r := mid.Next
	mid.Next = nil
	r = revertList(r)
	for r != nil {
		if l.Val != r.Val {
			return false
		}
		l = l.Next
		r = r.Next
	}
	return true
}

func getMiddle(head *ListNode) *ListNode {
	slow := head
	fast := head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

func revertList(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		tmp := cur.Next
		cur.Next = prev
		prev = cur
		cur = tmp
	}
	return prev
}

/**
 * @Description: 剑指 Offer II 032. 有效的变位词 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/18 9:14
 **/
func isAnagram(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}
	var seen = make([]byte, 26)
	for i := 0; i < len(s); i++ {
		seen[s[i]-'a']++
		seen[t[i]-'a']--
	}
	for i := 0; i < 26; i++ {
		if seen[i] != 0 {
			return false
		}
	}
	return true
}

/**
 * @Description: 剑指 Offer II 034. 外星语言是否排序 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/18 9:26
 **/
func isAlienSorted(words []string, order string) bool {
	var compare = make([]uint8, 26)
	for i := 0; i < 26; i++ {
		compare[order[i]-'a'] = uint8(i)
	}

	for i := 1; i < len(words); i++ {
		if len(words[i]) > len(words[i-1]) {
			for j := 0; j < len(words[i-1]); j++ {
				if compare[words[i][j]-'a'] < compare[words[i-1][j]-'a'] {
					return false
				} else if compare[words[i][j]-'a'] > compare[words[i-1][j]-'a'] {
					break
				}
			}
		} else {
			var j int
			for j < len(words[i]) {
				if compare[words[i][j]-'a'] < compare[words[i-1][j]-'a'] {
					return false
				} else if compare[words[i][j]-'a'] > compare[words[i-1][j]-'a'] {
					break
				}
				j++
			}
			if words[i] < words[i-1] && j == len(words[i]) {
				return false
			}
		}
	}
	return true
}

/**
 * @Description: 剑指 Offer II 101. 分割等和子集 简单
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/7/18 9:58
 **/
func canPartition101(nums []int) bool {
	if len(nums) == 1 {
		return false
	}
	total := 0
	for _, v := range nums {
		total += v
	}
	if total%2 == 1 {
		return false
	}
	targetSum := total / 2
	dp := make([][]bool, len(nums))
	for i, v := range nums {
		dp[i] = make([]bool, targetSum+1)
		for j := 0; j <= targetSum; j++ {
			if j == 0 {
				dp[i][j] = true
			}
			if v <= targetSum {
				dp[i][v] = true
			}
			if i > 0 {
				dp[i][j] = dp[i][j] || dp[i-1][j] || v <= j && dp[i-1][j-v]
			}
		}
	}
	return dp[len(nums)-1][targetSum]
}

/**
 * @Description: 剑指 Offer II 042. 最近请求次数 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/7/18 13:01
 **/
type RecentCounter struct {
	counter []int
	left    int
	right   int
}

func Constructor042() RecentCounter {
	return RecentCounter{
		counter: make([]int, 10001),
	}
}

func (this *RecentCounter) Ping(t int) int {
	this.counter[this.right] = t
	this.right++
	for this.counter[this.left] < t-3000 {
		this.left++
	}
	return this.right - this.left
}

/**
* @Description: 剑指 Offer II 052. 展平二叉搜索树 简单
* @Keyword: 左中右  具体地，当我们遍历到一个节点时，把它的左孩子设为空，并将其本身作为上一个遍历到的节点的右孩子。
  递归遍历的过程中，由于递归函数的调用栈保存了节点的引用
* @Author: kami
* @Date: 2022/7/18 13:29
**/
func increasingBST(root *TreeNode) *TreeNode {
	var cur = &TreeNode{}
	var res = cur
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)
		cur.Right = node
		node.Left = nil
		cur = cur.Right
		inorder(node.Right)
	}

	inorder(root)
	return res.Right
}

/**
 * @Description: 剑指 Offer II 056. 二叉搜索树中两个节点之和 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/7/19 11:30
 **/
func findTarget056(root *TreeNode, k int) bool {
	r := []int{}
	var inorder func(*TreeNode)
	inorder = func(root *TreeNode) {
		if root == nil {
			return
		}
		inorder(root.Left)
		r = append(r, root.Val)
		inorder(root.Right)
	}
	inorder(root)
	i, j := 0, len(r)-1
	for i < j {
		s := r[i] + r[j]
		if s == k {
			return true
		} else if s > k {
			j--
		} else {
			i++
		}
	}
	return false
}

/**
 * @Description: 剑指 Offer II 059. 数据流的第 K 大数值 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/7/19 11:41
 **/
type KthLargest struct {
	sort.IntSlice
	k int
}

func Constructor059(k int, nums []int) KthLargest {
	kl := KthLargest{k: k}
	for _, val := range nums {
		kl.Add(val)
	}
	return kl
}

func (kl *KthLargest) Push(v interface{}) {
	kl.IntSlice = append(kl.IntSlice, v.(int))
}

func (kl *KthLargest) Pop() interface{} {
	a := kl.IntSlice
	v := a[len(a)-1]
	kl.IntSlice = a[:len(a)-1]
	return v
}

func (kl *KthLargest) Add(val int) int {
	heap.Push(kl, val)
	if kl.Len() > kl.k {
		heap.Pop(kl)
	}
	return kl.IntSlice[0]
}

/**
 * @Description: 剑指 Offer II 068. 查找插入位置 简单
 * @Keyword: 二分查找
 * @Author: kami
 * @Date: 2022/7/19 11:48
 **/
func searchInsert(nums []int, target int) int {
	var left = 0
	var right = len(nums) - 1
	for left <= right {
		var mid = (left + right) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

/**
 * @Description: 剑指 Offer II 069. 山峰数组的顶部 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/19 11:58
 **/
func peakIndexInMountainArray(arr []int) int {
	for i := 1; i < len(arr)-1; i++ {
		if arr[i] > arr[i-1] && arr[i] > arr[i+1] {
			return i
		}
	}
	return -1
}

/**
 * @Description: 剑指 Offer II 072. 求平方根
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/19 12:01
 **/
func mySqrt(x int) int {
	var start = 0
	var end = x
	var res = -1
	for start <= end {
		var mid = (start + end) / 2
		if mid*mid <= x {
			start = mid + 1
			res = mid
		} else {
			end = mid - 1
		}
	}
	return res
}

/**
 * @Description: 剑指 Offer II 075. 数组相对排序  简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/19 12:13
 **/
func relativeSortArray(arr1 []int, arr2 []int) []int {
	var exist = make(map[int]int)
	for i := 0; i < len(arr2); i++ {
		exist[arr2[i]]++
	}
	var res []int
	var left []int
	for i := 0; i < len(arr1); i++ {
		if _, ok := exist[arr1[i]]; ok {
			exist[arr1[i]]++
		} else {
			left = append(left, arr1[i])
		}
	}
	for i := 0; i < len(arr2); i++ {
		var cnt = exist[arr2[i]] - 1
		for j := 0; j < cnt; j++ {
			res = append(res, arr2[i])
		}
	}
	sort.Ints(left)
	res = append(res, left...)
	return res
}

/**
 * @Description: 剑指 Offer II 081. 允许重复选择元素的组合 中等
 * @Keyword: 回溯
 * @Author: kami
 * @Date: 2022/7/19 12:43
 **/
func combinationSum081(candidates []int, target int) [][]int {
	var res [][]int
	var traceBack func(nums, curRes []int, idx, sum int)
	traceBack = func(nums, curRes []int, idx, sum int) {
		if sum > target {
			return
		}
		if sum == target {
			var tmp = make([]int, len(curRes))
			copy(tmp, curRes)
			res = append(res, tmp)
			return
		}

		for i := idx; i < len(nums); i++ {
			curRes = append(curRes, candidates[i])
			sum += candidates[i]
			traceBack(candidates, curRes, i, sum)
			sum -= candidates[i]
			curRes = curRes[0 : len(curRes)-1]
		}
	}
	traceBack(candidates, []int{}, 0, 0)
	return res
}

/**
 * @Description: 剑指 Offer II 082. 含有重复元素集合的组合 中等
 * @Keyword: 排序，回溯
 * @Author: kami
 * @Date: 2022/7/19 13:04
 **/
func combinationSum2(candidates []int, target int) [][]int {
	var res [][]int
	var traceBack func(nums, curRes []int, idx, sum int)

	traceBack = func(nums, curRes []int, idx, sum int) {
		if sum > target {
			return
		}
		if sum == target {
			var tmp = make([]int, len(curRes))
			copy(tmp, curRes)
			res = append(res, tmp)
			return
		}

		for i := idx; i < len(nums); i++ {
			if i > idx && nums[i] == nums[i-1] {
				continue
			}
			curRes = append(curRes, candidates[i])
			sum += candidates[i]
			traceBack(candidates, curRes, i+1, sum)
			sum -= candidates[i]
			curRes = curRes[0 : len(curRes)-1]
		}
	}
	sort.Ints(candidates)
	traceBack(candidates, []int{}, 0, 0)
	return res
}

/**
 * @Description: 剑指 Offer II 004. 只出现一次的数字 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/19 15:59
 **/
func singleNumber004(nums []int) int {
	ans := int32(0)
	for i := 0; i < 32; i++ {
		total := int32(0)
		for _, num := range nums {
			total += int32(num) >> i & 1
		}
		if total%3 > 0 {
			ans |= 1 << i
		}
	}
	return int(ans)
}

/**
 * @Description: 剑指 Offer II 083. 没有重复元素集合的全排列 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/19 16:38
 **/
func permute083(nums []int) [][]int {
	var res [][]int
	var visited = make([]bool, len(nums))
	var traceBack func(nums, curRes []int, visited []bool)
	traceBack = func(nums, curRes []int, visited []bool) {
		if len(curRes) == len(nums) {
			var tmp = make([]int, len(nums))
			copy(tmp, curRes)
			res = append(res, tmp)
			return
		}
		for i := 0; i < len(nums); i++ {
			if visited[i] {
				continue
			}
			curRes = append(curRes, nums[i])
			visited[i] = true
			traceBack(nums, curRes, visited)
			curRes = curRes[0 : len(curRes)-1]
			visited[i] = false
		}
	}

	traceBack(nums, []int{}, visited)
	return res
}

/**
 * @Description:剑指 Offer II 084. 含有重复元素集合的全排列 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/19 16:50
 **/
func permuteUnique084(nums []int) [][]int {
	sort.Ints(nums)
	n := len(nums)
	perm := []int{}
	var ans [][]int
	vis := make([]bool, n)
	var backtrack func(int)
	backtrack = func(idx int) {
		if idx == n {
			ans = append(ans, append([]int(nil), perm...))
			return
		}
		for i, v := range nums {
			if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {
				continue
			}
			perm = append(perm, v)
			vis[i] = true
			backtrack(idx + 1)
			vis[i] = false
			perm = perm[:len(perm)-1]
		}
	}
	backtrack(0)
	return ans
}

/**
 * @Description: 剑指 Offer II 005. 单词长度的最大乘积 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/19 17:07
 **/
func maxProduct005(words []string) (ans int) {
	masks := make([]int, len(words))
	for i, word := range words {
		for _, ch := range word {
			masks[i] |= 1 << (ch - 'a')
		}
	}

	for i, x := range masks {
		for j, y := range masks[:i] {
			if x&y == 0 && len(words[i])*len(words[j]) > ans {
				ans = len(words[i]) * len(words[j])
			}
		}
	}
	return
}

func maxProduct0051(words []string) (ans int) {
	masks := map[int]int{}
	for _, word := range words {
		mask := 0
		for _, ch := range word {
			mask |= 1 << (ch - 'a')
		}
		if len(word) > masks[mask] {
			masks[mask] = len(word)
		}
	}

	for x, lenX := range masks {
		for y, lenY := range masks {
			if x&y == 0 && lenX*lenY > ans {
				ans = lenX * lenY
			}
		}
	}
	return
}

/**
 * @Description: 剑指 Offer II 085. 生成匹配的括号 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/20 10:26
 **/
func generateParenthesis085(n int) []string {
	var traceBack func(left, right int, cur string)
	var res []string
	traceBack = func(left, right int, cur string) {
		if left < 0 || right < 0 || right < left {
			return
		}

		if right == 0 && left == 0 {
			res = append(res, cur)
			return
		}
		traceBack(left-1, right, cur+"(")
		traceBack(left, right-1, cur+")")
	}
	traceBack(n, n, "")
	return res
}

/**
 * @Description: 剑指 Offer II 007. 数组中和为 0 的三个数 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/20 11:17
 **/
func threeSum007(nums []int) [][]int {
	if len(nums) < 3 {
		return [][]int{}
	}
	sort.Ints(nums)
	if nums[0] > 0 || nums[len(nums)-1] < 0 {
		return [][]int{}
	}
	if nums[0] == 0 && nums[nums[len(nums)-1]] == 0 {
		return [][]int{{0, 0, 0}}
	}
	var res [][]int
	var preVal = math.MinInt
	for i := 0; i < len(nums)-2; i++ {
		if nums[i] == preVal {
			continue
		}
		var left = i + 1
		var right = len(nums) - 1
		for left < right {
			var sum = nums[left] + nums[right]
			if sum == -nums[i] {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				for left < right && nums[left+1] == nums[left] {
					left++
				}
				left++
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				right--
			} else if sum > -nums[i] {
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				right--
			} else {
				for left < right && nums[left+1] == nums[left] {
					left++
				}
				left++
			}
		}

		preVal = nums[i]
	}
	return res
}

/**
 * @Description: 剑指 Offer II 086. 分割回文子字符串 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/20 11:58
 **/
func partition086(s string) [][]string {
	var res [][]string
	var dfs func(s string, idx int, cur []string)

	dfs = func(s string, start int, cur []string) {
		if start == len(s) {
			var tmp = make([]string, len(cur))
			copy(tmp, cur)
			res = append(res, tmp)
			return
		}
		for i := start; i < len(s); i++ {
			if isPalid(s, start, i) {
				cur = append(cur, s[start:i+1])
				dfs(s, i+1, cur)
				cur = cur[0 : len(cur)-1]
			}
		}
	}
	dfs(s, 0, []string{})
	return res
}

func isPalid(s string, l, r int) bool {
	for l < r {
		if s[l] != s[r] {
			return false
		}
		l++
		r--
	}
	return true
}

/**
 * @Description: 剑指 Offer II 087. 复原 IP  中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/21 13:27
 **/
func restoreIpAddresses087(s string) []string {
	var res []string
	n := len(s)
	if n < 4 || n > 12 {
		return res
	}
	var tmp []string
	var dfs func(idx, cnt int)
	dfs = func(idx, cnt int) {
		if idx == n {
			if cnt == 4 {
				res = append(res, strings.Join(tmp, "."))
			}
			return
		}
		if cnt == 4 {
			return
		}
		for i := 1; i <= 3 && idx+i <= n; i++ {
			num, _ := strconv.Atoi(s[idx : idx+i])
			if num > 255 {
				break
			}
			tmp = append(tmp, s[idx:idx+i])
			dfs(idx+i, cnt+1)
			tmp = tmp[:len(tmp)-1]
			if s[idx] == '0' {
				break
			}
		}
	}
	dfs(0, 0)
	return res
}

/**
 * @Description: 剑指 Offer II 008. 和大于等于 target 的最短子数组 中等
 * @Keyword: 滑动窗口，左右指针
 * @Author: kami
 * @Date: 2022/7/22 11:07
 **/
func minSubArrayLen(target int, nums []int) int {
	var min = len(nums) + 1
	var left int
	var right int
	var sum int
	for right < len(nums) {
		sum += nums[right]
		if sum >= target {
			for left <= right && sum >= target {
				if right-left+1 < min {
					min = right - left + 1
				}
				sum -= nums[left]
				left++
			}
		}
		right++
	}
	if min > len(nums) {
		return 0
	}
	return min
}

/**
 * @Description: 剑指 Offer II 009. 乘积小于 K 的子数组 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/22 12:09
 **/
func numSubarrayProductLessThanK(nums []int, k int) int {
	var cnt int
	for i := 0; i < len(nums); i++ {
		var sum = 1
		for j := i; j < len(nums); i++ {
			sum *= nums[i]
			if sum < k {
				cnt++
			} else {
				break
			}
		}
	}
	return cnt
}

/**
 * @Description: 剑指 Offer II 089. 房屋偷盗 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/22 12:36
 **/
func rob(nums []int) int {

	var rob = nums[0]
	var notRob = 0
	for i := 1; i < len(nums); i++ {
		// 抢
		var newRob = notRob + nums[i]

		// 不抢
		if notRob < rob {
			notRob = rob
		}
		rob = newRob
	}
	if rob > notRob {
		return rob
	}
	return notRob
}

/**
 * @Description: 剑指 Offer II 010. 和为 k 的子数组 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/22 12:52
 **/
func subarraySum010(nums []int, k int) int {
	var cnt int
	for i := 0; i < len(nums); i++ {
		var sum int
		for j := i; j < len(nums); j++ {
			sum += nums[j]
			if sum == k {
				cnt++
			}
		}
	}
	return cnt
}
func subarraySum0100(nums []int, k int) int {
	count, pre := 0, 0
	m := map[int]int{}
	m[0] = 1
	for i := 0; i < len(nums); i++ {
		pre += nums[i]
		if _, ok := m[pre-k]; ok {
			count += m[pre-k]
		}
		m[pre] += 1
	}
	return count
}

/**
 * @Description: 剑指 Offer II 011. 0 和 1 个数相同的子数组 中等
 * @Keyword: 前缀和
 * @Author: kami
 * @Date: 2022/7/22 13:16
 **/
func findMaxLength(nums []int) int {
	var maxLength int
	mp := map[int]int{0: -1}
	counter := 0
	for i, num := range nums {
		if num == 1 {
			counter++
		} else {
			counter--
		}
		if prevIndex, has := mp[counter]; has {
			if i-prevIndex > maxLength {
				maxLength = i - prevIndex
			}
		} else {
			mp[counter] = i
		}
	}
	return maxLength

}

/**
 * @Description: 剑指 Offer II 013. 二维子矩阵的和 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/23 10:21
 **/
type NumMatrix struct {
	dpSum [][]int
}

func Constructor013(matrix [][]int) NumMatrix {
	dpSum := make([][]int, len(matrix))
	var sum int
	for i := 0; i < len(matrix); i++ {
		dpSum[i] = make([]int, len(matrix[0]))
		for j := 0; j < len(matrix[0]); j++ {
			dpSum[i][j] = sum + matrix[i][j]
			sum = dpSum[i][j]
		}
	}
	return NumMatrix{
		dpSum: dpSum,
	}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	var sum int
	var maxCol = len(this.dpSum[0]) - 1
	for i := row1; i <= row2; i++ {
		// 如果是第0行
		if i == 0 {
			// 起始为0列
			if col1 == 0 {
				sum += this.dpSum[i][col2]
			} else {
				sum += this.dpSum[i][col2] - this.dpSum[i][col1-1]
			}
		} else {
			// 起始为0列
			if col1 == 0 {
				sum += this.dpSum[i][col2] - this.dpSum[i-1][maxCol]
			} else {
				sum += this.dpSum[i][col2] - this.dpSum[i][col1-1]
			}
		}
	}
	return sum
}

/**
 * @Description: 剑指 Offer II 014. 字符串中的变位词 中等
 * @Keyword: 滑动窗口
 * @Author: kami
 * @Date: 2022/7/23 12:03
 **/
func checkInclusion(s1, s2 string) bool {
	n, m := len(s1), len(s2)
	if n > m {
		return false
	}
	var cnt1, cnt2 [26]int
	for i, ch := range s1 {
		cnt1[ch-'a']++
		cnt2[s2[i]-'a']++
	}
	if cnt1 == cnt2 {
		return true
	}
	for i := n; i < m; i++ {
		cnt2[s2[i]-'a']++
		cnt2[s2[i-n]-'a']--
		if cnt1 == cnt2 {
			return true
		}
	}
	return false
}
func checkInclusion014(s1, s2 string) bool {
	n, m := len(s1), len(s2)
	if n > m {
		return false
	}
	cnt := [26]int{}
	for _, ch := range s1 {
		cnt[ch-'a']--
	}
	left := 0
	for right, ch := range s2 {
		x := ch - 'a'
		cnt[x]++
		for cnt[x] > 0 {
			cnt[s2[left]-'a']--
			left++
		}
		if right-left+1 == n {
			return true
		}
	}
	return false
}

/**
 * @Description: 剑指 Offer II 015. 字符串中的所有变位词 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/23 12:38
 **/
func findAnagrams(s string, p string) []int {
	n, m := len(s), len(p)
	if m > n {
		return nil
	}

	cnt := [26]int{}
	for i := range p {
		cnt[p[i]-'a']--
	}

	var lo, hi int
	ret := make([]int, 0)
	for hi < len(s) {
		x := s[hi] - 'a'
		cnt[x]++

		for cnt[x] > 0 {
			cnt[s[lo]-'a']--
			lo++
		}
		if hi-lo+1 == m {
			ret = append(ret, lo)
			cnt[s[lo]-'a']--
			lo++
		}
		hi++
	}

	return ret
}

/**
 * @Description: 剑指 Offer II 016. 不含重复字符的最长子字符串 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/23 13:04
 **/
func lengthOfLongestSubstring016(s string) int {
	var seen = make(map[byte]int)
	var left int
	var right int
	var max int
	for right < len(s) {
		if idx, ok := seen[s[right]]; ok {
			if len(seen) > max {
				max = len(seen)
			}
			for i := left; i <= idx; i++ {
				delete(seen, s[i])
			}
			left = idx + 1
		}
		seen[s[right]] = right
		right++
	}
	if len(seen) > max {
		max = len(seen)
	}
	return max
}

/**
 * @Description: 剑指 Offer II 020. 回文子字符串的个数
 * @Keyword: 中心扩展
 * @Author: kami
 * @Date: 2022/7/23 13:20
 **/
func countSubstrings020(s string) int {
	var cnt int
	for i := 0; i < len(s); i++ {
		cnt += center(s, i) + left(s, i)
	}
	return cnt
}

func center(s string, mid int) int {
	var cnt = 1
	var left = mid - 1
	var right = mid + 1
	for left >= 0 && right < len(s) {
		if s[left] != s[right] {
			return cnt
		}
		cnt++
		left--
		right++
	}
	return cnt
}
func left(s string, left int) int {
	var cnt int
	var right = left + 1
	for left >= 0 && right < len(s) {
		if s[left] != s[right] {
			return cnt
		}
		cnt++
		left--
		right++
	}
	return cnt
}

/**
 * @Description: 剑指 Offer II 021. 删除链表的倒数第 n 个结点 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/23 13:29
 **/
func removeNthFromEnd021(head *ListNode, n int) *ListNode {
	var nNode = head
	var cnt = 1
	for cnt < n {
		nNode = nNode.Next
		cnt++
	}
	var deleteNode = head
	var preNode *ListNode
	for nNode.Next != nil {
		preNode = deleteNode
		deleteNode = deleteNode.Next
		nNode = nNode.Next
	}
	if preNode != nil {
		preNode.Next = deleteNode.Next
		return head
	}
	return head.Next
}

/**
 * @Description: 剑指 Offer II 022. 链表中环的入口节点 中等
 * @Keyword: 快慢指针
 * @Author: kami
 * @Date: 2022/7/23 13:45
 **/
func detectCycle022(head *ListNode) *ListNode {
	var slow = head
	var quick = head
	for quick != nil || quick.Next != nil {
		slow = slow.Next
		quick = quick.Next.Next
		if slow == quick {
			slow = head
			for slow != quick {
				slow = slow.Next
				quick = quick.Next
			}
			return slow
		}
	}
	return nil

}

/**
 * @Description: 剑指 Offer II 025. 链表中的两数相加 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/23 14:29
 **/
func addTwoNumbers025(l1 *ListNode, l2 *ListNode) *ListNode {
	var num1 = make([]uint8, 0)
	var cur1 = l1
	for cur1 != nil {
		num1 = append(num1, uint8(cur1.Val))
		cur1 = cur1.Next
	}
	var num2 = make([]uint8, 0)
	var cur2 = l2
	for cur2 != nil {
		num2 = append(num2, uint8(cur2.Val))
		cur2 = cur2.Next
	}
	var pre *ListNode
	var take uint8
	var idx = 1
	for idx <= len(num1) || idx <= len(num2) {
		var sum uint8
		if idx <= len(num1) && idx <= len(num2) {
			sum = num1[len(num1)-idx] + num2[len(num2)-idx] + take
		} else if idx <= len(num1) {
			sum = num1[len(num1)-idx] + take
		} else {
			sum = num2[len(num2)-idx] + take
		}

		if sum > 9 {
			take = 1
		} else {
			take = 0
		}
		node := &ListNode{Val: int(sum % 10), Next: pre}
		pre = node
		idx++
	}
	if take > 0 {
		return &ListNode{Val: 1, Next: pre}
	}
	return pre

}

/**
 * @Description: 剑指 Offer II 026. 重排链表 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/24 14:29
 **/
func reorderList(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}
	var slow = head
	var fast = head
	var pre *ListNode
	for fast != nil && fast.Next != nil {
		pre = slow
		slow = slow.Next
		fast = fast.Next.Next
	}
	pre.Next = nil

	var tail = reverse1(slow)

	var cur = head
	for cur != nil && tail != nil {
		next := cur.Next
		cur.Next = tail
		if next == nil {
			return
		}
		tailNext := tail.Next
		tail.Next = next
		cur = next
		tail = tailNext
	}

}

func reverse1(head *ListNode) *ListNode {
	var cur = head
	var pre *ListNode
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

/**
 * @Description: 剑指 Offer II 028. 展平多级双向链表 中等
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/7/24 15:02
 **/
func flatten028(root *Node028) *Node028 {
	if root == nil {
		return nil
	}
	var dfs func(root *Node028) *Node028
	dfs = func(root *Node028) *Node028 {
		tail, next := root, root.Next
		if root.Child != nil {
			root.Next = root.Child
			root.Child.Prev = root
			tail = dfs(root.Child)
			root.Child = nil
			tail.Next = next
		}
		if next == nil {
			return tail
		}

		next.Prev = tail

		return dfs(next)
	}
	dfs(root)
	return root

}

type Node028 struct {
	Val   int
	Prev  *Node028
	Next  *Node028
	Child *Node028
}

/**
 * @Description: 剑指 Offer II 029. 排序的循环链表 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/24 16:12
 **/
func insert(head *Node, insertVal int) *Node {
	node := &Node{Val: insertVal}
	if head == nil {
		node.Next = node
		return node
	}
	if head.Next == head {
		head.Next = node
		node.Next = head
		return head
	}
	curr, next := head, head.Next
	for next != head {
		if insertVal >= curr.Val && insertVal <= next.Val {
			break
		}
		if curr.Val > next.Val {
			if insertVal > curr.Val || insertVal < next.Val {
				break
			}
		}
		curr = curr.Next
		next = next.Next
	}
	curr.Next = node
	node.Next = next
	return head
}

/**
 * @Description: 剑指 Offer II 044. 二叉树每层的最大值 中等
 * @Keyword: 二叉树层序遍历
 * @Author: kami
 * @Date: 2022/7/25 10:52
 **/
func largestValues(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	if root.Left == nil && root.Right == nil {
		return []int{root.Val}
	}
	var stack = []*TreeNode{root}
	var res []int
	for len(stack) > 0 {
		var next []*TreeNode
		var max = stack[0].Val
		for i := 0; i < len(stack); i++ {
			if stack[i].Val > max {
				max = stack[i].Val
			}
			if stack[i].Left != nil {
				next = append(next, stack[i].Left)
			}
			if stack[i].Right != nil {
				next = append(next, stack[i].Right)
			}
		}
		res = append(res, max)
		stack = next
	}
	return res
}

/**
 * @Description: 剑指 Offer II 090. 环形房屋偷盗 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/25 10:59
 **/
func rob090(nums []int) int {
	if len(nums) == 2 {
		if nums[0] > nums[1] {
			return nums[0]
		}
		return nums[1]
	}
	if len(nums) == 1 {
		return nums[0]
	}
	var robVal = dynamicRob(nums[0 : len(nums)-1])
	var notRobVal = dynamicRob(nums[1:])
	if robVal > notRobVal {
		return robVal
	}
	return notRobVal
}

func dynamicRob(nums []int) int {

	var dp = make([][2]int, len(nums))
	dp[0][1] = nums[0]
	for i := 1; i < len(nums); i++ {
		dp[i][1] = dp[i-1][0] + nums[i]

		if dp[i-1][0] > dp[i-1][1] {
			dp[i][0] = dp[i-1][0]
		} else {
			dp[i][0] = dp[i-1][1]
		}
	}
	var r = len(nums) - 1
	if dp[r][0] > dp[r][1] {
		return dp[r][0]
	}
	return dp[r][1]
}

/**
 * @Description:剑指 Offer II 092. 翻转字符 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/25 17:37
 **/
func minFlipsMonoIncr(s string) int {
	// 要通过翻转01把整个序列变为0在前1在后，那么我们可以在序列中找到一个点，这个点之前的1全部翻转为0，这个点之后的0全部翻转为1使得总翻转次数最小。
	var ans int
	var oneCnt int
	for i := 0; i < len(s); i++ {
		if s[i] == '1' {
			// 记录前面为1 的个数
			oneCnt++
			continue
		}
		// s【i】 == 0 ，看反转前面全是 1 的为0 和 反转当前为1的代价哪个大
		ans = getMin(oneCnt, ans+1)
	}
	return ans
}

/**
 * @Description: 剑指 Offer II 045. 二叉树最底层最左边的值 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/25 18:37
 **/
func findBottomLeftValue(root *TreeNode) int {
	var stack = []*TreeNode{root}
	for len(stack) > 0 {
		var next []*TreeNode
		for i := 0; i < len(stack); i++ {
			if stack[i].Left != nil {
				next = append(next, stack[i].Left)
			}
			if stack[i].Right != nil {
				next = append(next, stack[i].Right)
			}
		}
		if len(next) == 0 {
			return stack[0].Val
		}
		stack = next
	}
	return stack[0].Val
}

/**
 * @Description: 剑指 Offer II 076. 数组中的第 k 大的数字
 * @Keyword: 快速排序
 * @Author: kami
 * @Date: 2022/7/25 18:46
 **/
func findKthLargest(nums []int, k int) int {
	n := len(nums)
	x := rand.Intn(n)
	// 随机数放在最右边
	nums[x], nums[n-1] = nums[n-1], nums[x]
	l := 0
	r := n - 1
	var val = nums[n-1]
	// 从大到小排序
	for l < r {
		for l < r && nums[l] >= val {
			l++
		}
		for l < r && val >= nums[r] {
			r--
		}
		if l < r {
			nums[l], nums[r] = nums[r], nums[l]
		}
	}
	if r == k-1 {
		return val
	} else if r < k-1 {
		nums[r], nums[n-1] = nums[n-1], nums[r]
		return findKthLargest(nums[r+1:], k-(r+1))
	} else {
		return findKthLargest(nums[:r], k)
	}

}

/**
 * @Description: 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/27 8:53
 **/
type RandomizedSet struct {
	m   map[int]int
	arr []int
}

/** Initialize your data structure here. */
func Constructor030() RandomizedSet {
	return RandomizedSet{
		m:   map[int]int{},
		arr: []int{},
	}
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.m[val]; ok {
		return false
	} else {
		this.arr = append(this.arr, val)
		this.m[val] = len(this.arr) - 1
		return true
	}
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
	if idx, ok := this.m[val]; ok {
		var lastIdx = len(this.arr) - 1
		if lastIdx != idx {
			this.arr[idx] = this.arr[lastIdx]
			this.m[this.arr[idx]] = idx
		}
		this.arr = this.arr[0:lastIdx]
		delete(this.m, val)

		return true
	}

	return false

}

/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
	if len(this.arr) == 0 {
		return -1
	}
	//rand.Seed(time.Now().Unix())
	var idx = rand.Intn(len(this.arr))
	return this.arr[idx]
}

/**
 * @Description:剑指 Offer II 091. 粉刷房子 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/7/27 9:16
 **/
func minCost(costs [][]int) int {
	var dp = make([][3]int, len(costs))
	dp[0][0] = costs[0][0]
	dp[0][1] = costs[0][1]
	dp[0][2] = costs[0][2]
	for i := 1; i < len(costs); i++ {
		dp[i][0] = costs[i][0] + getMin(dp[i-1][1], dp[i-1][2])
		dp[i][1] = costs[i][1] + getMin(dp[i-1][0], dp[i-1][2])
		dp[i][2] = costs[i][2] + getMin(dp[i-1][0], dp[i-1][1])
	}
	var last = len(costs) - 1
	return getMin(dp[last][0], dp[last][1], dp[last][2])
}

/**
 * @Description: 剑指 Offer II 031. 最近最少使用缓存 中等
 * @Keyword: 哈希表加双向链表
 * @Author: kami
 * @Date: 2022/7/27 9:39
 **/
type LRUCache031 struct {
	size       int
	capacity   int
	cache      map[int]*DLinkedNode
	head, tail *DLinkedNode
}

type DLinkedNode struct {
	key, value int
	prev, next *DLinkedNode
}

func initDLinkedNode(key, value int) *DLinkedNode {
	return &DLinkedNode{
		key:   key,
		value: value,
	}
}

func Constructor031(capacity int) LRUCache031 {
	l := LRUCache031{
		cache:    map[int]*DLinkedNode{},
		head:     initDLinkedNode(0, 0),
		tail:     initDLinkedNode(0, 0),
		capacity: capacity,
	}
	l.head.next = l.tail
	l.tail.prev = l.head
	return l
}

func (this *LRUCache031) Get031(key int) int {
	if _, ok := this.cache[key]; !ok {
		return -1
	}
	node := this.cache[key]
	this.moveToHead(node)
	return node.value
}

func (this *LRUCache031) Pu031(key int, value int) {
	if _, ok := this.cache[key]; !ok {
		node := initDLinkedNode(key, value)
		this.cache[key] = node
		this.addToHead(node)
		this.size++
		if this.size > this.capacity {
			removed := this.removeTail()
			delete(this.cache, removed.key)
			this.size--
		}
	} else {
		node := this.cache[key]
		node.value = value
		this.moveToHead(node)
	}
}

func (this *LRUCache031) addToHead(node *DLinkedNode) {
	node.prev = this.head
	node.next = this.head.next
	this.head.next.prev = node
	this.head.next = node
}

func (this *LRUCache031) removeNode(node *DLinkedNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (this *LRUCache031) moveToHead(node *DLinkedNode) {
	this.removeNode(node)
	this.addToHead(node)
}

func (this *LRUCache031) removeTail() *DLinkedNode {
	node := this.tail.prev
	this.removeNode(node)
	return node
}

/**
 * @Description: 剑指 Offer II 093. 最长斐波那契数列 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/28 17:11
 **/
func lenLongestFibSubseq(arr []int) (ans int) {
	n := len(arr)
	indices := make(map[int]int, n)
	for i, x := range arr {
		indices[x] = i
	}
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i, x := range arr {
		for j := i - 1; j >= 0; j-- {
			var pre = x - arr[j]
			if pre >= arr[j] {
				break
			}
			if v, ok := indices[pre]; ok {
				dp[i][j] = getMax(2, dp[j][v]) + 1
				ans = getMax(ans, dp[i][j])
			}
		}
	}
	return
}

/**
 * @Description: 剑指 Offer II 033. 变位词组 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/29 10:52
 **/
func groupAnagrams033(strs []string) [][]string {
	var exists = make(map[string][]string)
	var letter = []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"}
	var blank []string
	for i := 0; i < len(strs); i++ {
		if strs[i] == "" {
			blank = append(blank, "")
			continue
		}
		var dp = make([]int, 26)
		var curStr = strs[i]
		for j := 0; j < len(curStr); j++ {
			dp[curStr[j]-'a']++
		}
		var strExist string
		for k := 0; k < 26; k++ {
			if dp[k] > 0 {
				strExist += letter[k] + strconv.Itoa(dp[k])
			}
		}
		if strExist != "" {
			if val, ok := exists[strExist]; ok {
				val = append(val, curStr)
				exists[strExist] = val
			} else {
				exists[strExist] = []string{curStr}
			}
		}
	}
	var res [][]string
	for _, val := range exists {
		res = append(res, val)
	}
	if len(blank) > 0 {
		res = append(res, blank)
	}
	return res
}

/**
 * @Description: 剑指 Offer II 096. 字符串交织 中等
 * @Keyword: 回溯 会超时
 * @Author: kami
 * @Date: 2022/7/29 11:29
 **/
func isInterleave(s1 string, s2 string, s3 string) bool {
	if s1 == "" {
		return s2 == s3
	}
	if s2 == "" {
		return s1 == s3
	}
	if len(s1)+len(s2) != len(s3) {
		return false
	}
	var traceBack func(s1, s2, s3 string, s1Idx, s2Idx, s3Idx int) bool

	traceBack = func(s1, s2, s3 string, s1Idx, s2Idx, s3Idx int) bool {
		if s3Idx == len(s3)-1 && ((s1Idx == len(s1)-1 && s1[s1Idx] == s3[s3Idx]) || (s2Idx == len(s2)-1 && s2[s2Idx] == s3[s3Idx])) {
			return true
		}
		if s1Idx < len(s1) && s3Idx < len(s3) && s1[s1Idx] == s3[s3Idx] {
			if traceBack(s1, s2, s3, s1Idx+1, s2Idx, s3Idx+1) {
				return true
			}
		}
		if s2Idx < len(s2) && s3Idx < len(s3) && s2[s2Idx] == s3[s3Idx] {
			if traceBack(s1, s2, s3, s1Idx, s2Idx+1, s3Idx+1) {
				return true
			}
		}
		return false
	}

	return traceBack(s1, s2, s3, 0, 0, 0)
}

func isInterleave01(s1 string, s2 string, s3 string) bool {
	n, m, t := len(s1), len(s2), len(s3)
	if (n + m) != t {
		return false
	}
	f := make([][]bool, n+1)
	for i := 0; i <= n; i++ {
		f[i] = make([]bool, m+1)
	}
	f[0][0] = true
	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			p := i + j - 1
			if i > 0 {
				f[i][j] = f[i][j] || (f[i-1][j] && s1[i-1] == s3[p])
			}
			if j > 0 {
				f[i][j] = f[i][j] || (f[i][j-1] && s2[j-1] == s3[p])
			}
		}
	}
	return f[n][m]
}

/**
 * @Description: 剑指 Offer II 035. 最小时间差 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/29 15:24
 **/
func findMinDifference(timePoints []string) int {
	if len(timePoints) > 24*60 {
		return 0
	}
	var mins []int
	for _, t := range timePoints {
		time := strings.Split(t, ":")
		h, _ := strconv.Atoi(time[0])
		m, _ := strconv.Atoi(time[1])
		mins = append(mins, h*60+m)
	}
	sort.Ints(mins)
	mins = append(mins, mins[0]+24*60)
	res := 24 * 60
	for i := 1; i < len(mins); i++ {
		res = min(res, mins[i]-mins[i-1])
	}
	return res
}

/**
 * @Description: 剑指 Offer II 036. 后缀表达式 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/29 16:03
 **/
func evalRPN(tokens []string) int {
	var stack []int
	for i := 0; i < len(tokens); i++ {
		switch tokens[i] {
		case "+":
			var right = stack[len(stack)-1]
			var left = stack[len(stack)-2]
			var res = left + right
			stack[len(stack)-2] = res
			stack = stack[0 : len(stack)-1]
		case "-":
			var right = stack[len(stack)-1]
			var left = stack[len(stack)-2]
			var res = left - right
			stack[len(stack)-2] = res
			stack = stack[0 : len(stack)-1]
		case "*":
			var right = stack[len(stack)-1]
			var left = stack[len(stack)-2]
			var res = left * right
			stack[len(stack)-2] = res
			stack = stack[0 : len(stack)-1]
		case "/":
			var right = stack[len(stack)-1]
			var left = stack[len(stack)-2]
			var res = left / right
			stack[len(stack)-2] = res
			stack = stack[0 : len(stack)-1]
		default:
			num, _ := strconv.Atoi(tokens[i])
			stack = append(stack, num)
		}
	}
	return stack[0]
}

/**
 * @Description: 剑指 Offer II 037. 小行星碰撞 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/29 16:35
 **/
func asteroidCollision(asteroids []int) []int {
	var res []int
	for i := 0; i < len(asteroids); i++ {
		if len(res) == 0 || res[len(res)-1] < 0 || asteroids[i] > 0 {
			res = append(res, asteroids[i])
			continue
		}
		// + -
		var cur = asteroids[i]
		for len(res) > 0 {
			var pre = res[len(res)-1]
			var sum = cur + pre
			if pre < 0 {
				res = append(res, cur)
				break
			}
			if sum > 0 {
				break
			} else if sum == 0 {
				res = res[0 : len(res)-1]
				break
			} else {
				if len(res) == 1 {
					res[0] = cur
					break
				}
				res = res[0 : len(res)-1]
			}
		}

	}
	return res
}

/**
 * @Description: 剑指 Offer II 038. 每日温度 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/29 18:10
 **/
func dailyTemperatures038(temperatures []int) []int {
	var res = make([]int, len(temperatures))
	var last = len(temperatures) - 1
	for i := last - 1; i >= 0; i-- {
		var cur = temperatures[i]
		var idx = i + 1
		for idx < len(temperatures) {
			if temperatures[idx] > cur {
				res[i] = idx - i
				break
			} else if res[idx] == 0 {
				break
			}
			idx += res[idx]
		}
	}
	return res
}

/**
 * @Description: 剑指 Offer II 099. 最小路径之和 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/7/29 18:21
 **/
func minPathSum099(grid [][]int) int {
	var dp = make([][]int, len(grid))
	for i := 0; i < len(grid); i++ {
		dp[i] = make([]int, len(grid[0]))
	}
	// 第0列
	dp[0][0] = grid[0][0]
	for i := 1; i < len(grid); i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for i := 1; i < len(grid[0]); i++ {
		dp[0][i] = dp[0][i-1] + grid[0][i]
	}
	for i := 1; i < len(grid); i++ {
		for j := 1; j < len(grid[0]); j++ {
			dp[i][j] = getMin(dp[i-1][j], dp[i][j-1]) + grid[i][j]
		}
	}
	return dp[len(grid)-1][len(grid[0])-1]
}

/**
 * @Description: 剑指 Offer II 100. 三角形中最小路径之和 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/7/29 18:28
 **/
func minimumTotal(triangle [][]int) int {
	var dp = make([][]int, len(triangle))
	for i := 0; i < len(triangle); i++ {
		dp[i] = make([]int, i+1)
	}

	// 第0列 最后一列
	dp[0][0] = triangle[0][0]
	for i := 1; i < len(triangle); i++ {
		dp[i][0] = dp[i-1][0] + triangle[i][0]
		dp[i][i] = dp[i-1][i-1] + triangle[i][i]
	}
	for i := 1; i < len(triangle); i++ {
		for j := 1; j < len(triangle[i])-1; j++ {
			dp[i][j] = getMin(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
		}
	}

	var lastRow = len(triangle) - 1
	var res = dp[lastRow][0]
	for i := 1; i < len(triangle); i++ {
		if dp[lastRow][i] < res {
			res = dp[lastRow][i]
		}
	}
	return res
}

/**
 * @Description: 剑指 Offer II 102. 加减的目标值 中等
 * @Keyword: 动态规划，01背包
 * @Author: kami
 * @Date: 2022/7/29 18:57
 **/
func findTargetSumWays102(nums []int, target int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	diff := sum - target
	if diff < 0 || diff%2 == 1 {
		return 0
	}
	n, neg := len(nums), diff/2
	// dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, neg+1)
	}
	dp[0][0] = 1
	for i, num := range nums {
		for j := 0; j <= neg; j++ {
			dp[i+1][j] = dp[i][j]
			if j >= num {
				dp[i+1][j] += dp[i][j-num]
			}
		}
	}
	return dp[n][neg]
}

/**
 * @Description: 剑指 Offer II 103. 最少的硬币数目 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/7/29 21:20
 **/
func coinChange(coins []int, amount int) int {
	if amount == 0 {
		return 0
	}
	var dp = make([]int, amount+1)

	for i := 0; i <= amount; i++ {
		for j := 0; j < len(coins); j++ {
			if coins[j] == i {
				dp[i] = 1
			} else if coins[j] < i {
				if dp[i-coins[j]] != 0 {
					var cnt = dp[i-coins[j]] + 1
					if dp[i] == 0 || cnt < dp[i] {
						dp[i] = cnt
					}
				}

			}
		}
	}
	if dp[amount] == 0 {
		return -1
	}
	return dp[amount]
}

/**
 * @Description: 剑指 Offer II 104. 排列的数目 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/29 22:11
 **/
func combinationSum4(nums []int, target int) int {
	if target == 0 {
		return 0
	}
	var dp = make([]int, target+1)
	dp[0] = 1
	// dp[i] = dp[i-nums[0]] + dp[i-nums[1]] + ... + dp[i - nums[k]],
	for i := 0; i <= target; i++ {
		for j := 0; j < len(nums); j++ {
			if nums[j] <= i {
				dp[i] += dp[i-nums[j]]
			}
		}
	}

	return dp[target]
}

/**
 * @Description: 剑指 Offer II 105. 岛屿的最大面积 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/7/30 10:26
 **/
func maxAreaOfIsland(grid [][]int) int {
	var visited = make([][]bool, len(grid))
	for i := 0; i < len(grid); i++ {
		visited[i] = make([]bool, len(grid[0]))
	}
	var cnt int
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 && !visited[i][j] {
				var tmp = maxArea105(grid, visited, i, j)
				if tmp > cnt {
					cnt = tmp
				}
			}
		}
	}
	return cnt
}

func maxArea105(grid [][]int, visited [][]bool, row, col int) int {
	if row < 0 || row == len(grid) || col < 0 || col == len(grid[0]) || grid[row][col] == 0 || visited[row][col] {
		return 0
	}
	visited[row][col] = true
	var cnt = 1
	var upCnt = maxArea105(grid, visited, row-1, col)
	var downCnt = maxArea105(grid, visited, row+1, col)
	var leftCnt = maxArea105(grid, visited, row, col-1)
	var rightCnt = maxArea105(grid, visited, row, col+1)
	return cnt + upCnt + downCnt + leftCnt + rightCnt
}

/**
 * @Description: 剑指 Offer II 106. 二分图 中等
 * @Keyword: 深度优先遍历
 * @Author: kami
 * @Date: 2022/7/30 11:08
 **/
func isBipartite(graph [][]int) bool {
	n := len(graph)
	mark := make([]int, n)
	for i := range mark {
		mark[i] = -1
	}
	for i := 0; i < n; i++ {
		if mark[i] != -1 {
			continue
		}
		queue := []int{i}
		for len(queue) > 0 {
			u := queue[0]
			queue = queue[1:]
			for _, v := range graph[u] {
				if mark[v] != -1 {
					if mark[u]^mark[v] != 1 {
						return false
					}
				} else {
					mark[v] = mark[u] ^ 1
					queue = append(queue, v)
				}
			}
		}
	}
	return true
}

/**
 * @Description: 剑指 Offer II 043. 往完全二叉树添加节点  中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/30 11:09
 **/
type CBTInserter struct {
	root *TreeNode
	q    []*TreeNode
}

func Constructor043(root *TreeNode) CBTInserter {
	res := CBTInserter{
		root: root,
	}

	var deque = []*TreeNode{root}
	var q []*TreeNode
	for len(deque) > 0 {
		var node = deque[0]
		if node.Left == nil || node.Right == nil {
			q = append(q, node)
		}
		if node.Left != nil {
			deque = append(deque, node.Left)
		}
		if node.Right != nil {
			deque = append(deque, node.Right)
		}
		deque = deque[1:]
	}

	res.q = q
	return res
}

func (this *CBTInserter) Insert(v int) int {
	var node = this.q[0]
	this.q = this.q[1:]
	if node.Left == nil {
		node.Left = &TreeNode{Val: v}
		if node.Right == nil {
			this.q = append([]*TreeNode{node}, this.q...)
		}
		this.q = append(this.q, node.Left)
	} else {
		node.Right = &TreeNode{
			Val: v,
		}
		this.q = append(this.q, node.Right)
	}
	return node.Val
}

func (this *CBTInserter) Get_root() *TreeNode {
	return this.root
}

/**
 * @Description: 剑指 Offer II 107. 矩阵中的距离 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/7/31 10:17
 **/
func updateMatrix(mat [][]int) [][]int {
	var dp = make([][]int, len(mat))
	var m = len(mat)
	var n = len(mat[0])
	var max = m * n

	for i := 0; i < len(mat); i++ {
		dp[i] = make([]int, len(mat[i]))
		for j := 0; j < len(mat[0]); j++ {
			dp[i][j] = max
		}
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if mat[i][j] == 0 {
				dp[i][j] = 0
			}
			if i+1 < m {
				dp[i+1][j] = getMin(dp[i][j]+1, dp[i+1][j])
			}
			if j+1 < n {
				dp[i][j+1] = getMin(dp[i][j]+1, dp[i][j+1])
			}
		}
	}

	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if i-1 >= 0 {
				dp[i-1][j] = getMin(dp[i][j]+1, dp[i-1][j])
			}
			if j-1 >= 0 {
				dp[i][j-1] = getMin(dp[i][j]+1, dp[i][j-1])
			}
		}
	}
	return dp
}

/**
 * @Description: 剑指 Offer II 046. 二叉树的右侧视图 中等
 * @Keyword: 层序遍历
 * @Author: kami
 * @Date: 2022/7/31 11:55
 **/
func rightSideView(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	var res []int
	var stack = []*TreeNode{root}
	for len(stack) > 0 {
		res = append(res, stack[len(stack)-1].Val)
		var tmp []*TreeNode
		for i := 0; i < len(stack); i++ {
			if stack[i].Left != nil {
				tmp = append(tmp, stack[i].Left)
			}
			if stack[i].Right != nil {
				tmp = append(tmp, stack[i].Right)
			}
		}
		stack = tmp
	}
	return res
}

/**
 * @Description: 剑指 Offer II 047. 二叉树剪枝 中等
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/7/31 12:01
 **/
func pruneTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	// 返回值 是否都是0
	var dfs func(node *TreeNode) bool
	dfs = func(node *TreeNode) bool {
		if node == nil {
			return true
		}
		var left = dfs(node.Left)
		var right = dfs(node.Right)

		if left {
			node.Left = nil
		}
		if right {
			node.Right = nil
		}
		if left && right && node.Val == 0 {
			return true
		}

		return false
	}
	if dfs(root) {
		return nil
	}
	return root
}

/**
 * @Description: 剑指 Offer II 109. 开密码锁 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/31 12:29
 **/
func openLock(deadends []string, target string) int {
	const start = "0000"
	if target == start {
		return 0
	}

	dead := map[string]bool{}
	for _, s := range deadends {
		dead[s] = true
	}
	if dead[start] {
		return -1
	}

	// 枚举 status 通过一次旋转得到的数字
	get := func(status string) (ret []string) {
		s := []byte(status)
		for i, b := range s {
			s[i] = b - 1
			if s[i] < '0' {
				s[i] = '9'
			}
			ret = append(ret, string(s))
			s[i] = b + 1
			if s[i] > '9' {
				s[i] = '0'
			}
			ret = append(ret, string(s))
			s[i] = b
		}
		return
	}

	type pair struct {
		status string
		step   int
	}
	q := []pair{{start, 0}}
	seen := map[string]bool{start: true}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		for _, nxt := range get(p.status) {
			if !seen[nxt] && !dead[nxt] {
				if nxt == target {
					return p.step + 1
				}
				seen[nxt] = true
				q = append(q, pair{nxt, p.step + 1})
			}
		}
	}
	return -1
}

/**
 * @Description: 剑指 Offer II 110. 所有路径 z中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/1 11:28
 **/
func allPathsSourceTarget(graph [][]int) [][]int {

	var res [][]int
	var traceBack func(graph [][]int, visited []bool, curVisit []int)

	traceBack = func(graph [][]int, visited []bool, curVisit []int) {
		if len(curVisit) > 0 && curVisit[len(curVisit)-1] == len(graph)-1 {
			var tmp = make([]int, len(curVisit))
			copy(tmp, curVisit)
			res = append(res, tmp)
			return
		}
		var lastNode = curVisit[len(curVisit)-1]
		for i := 0; i < len(graph[lastNode]); i++ {
			if visited[graph[lastNode][i]] {
				continue
			}
			curVisit = append(curVisit, graph[lastNode][i])
			visited[graph[lastNode][i]] = true
			traceBack(graph, visited, curVisit)
			curVisit = curVisit[0 : len(curVisit)-1]
			visited[graph[lastNode][i]] = false
		}
	}
	var visited = make([]bool, len(graph))
	visited[0] = true
	traceBack(graph, visited, []int{0})
	return res
}

/**
 * @Description: 剑指 Offer II 049. 从根节点到叶节点的路径数字之和 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/1 11:59
 **/
func sumNumbers(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var sum int
	var dfs func(node *TreeNode, curVal int)
	dfs = func(node *TreeNode, curVal int) {
		curVal *= 10
		curVal += node.Val
		if node.Left == nil && node.Right == nil {
			sum += curVal
			return
		}

		if node.Left != nil {
			dfs(node.Left, curVal)
		}
		if node.Right != nil {
			dfs(node.Right, curVal)
		}
	}
	dfs(root, 0)
	return sum
}

/**
 * @Description: 剑指 Offer II 050. 向下的路径节点之和 中等
 * @Keyword: 前缀和
 * @Author: kami
 * @Date: 2022/8/1 12:21
 **/
func pathSum050(root *TreeNode, targetSum int) int {
	// 前缀和 :次数
	preSum := map[int64]int{0: 1}
	var ans int
	var dfs func(*TreeNode, int64)
	dfs = func(node *TreeNode, curr int64) {
		if node == nil {
			return
		}
		curr += int64(node.Val)
		ans += preSum[curr-int64(targetSum)]
		preSum[curr]++
		dfs(node.Left, curr)
		dfs(node.Right, curr)
		preSum[curr]--
		return
	}
	dfs(root, 0)
	return ans
}

/**
 * @Description: 剑指 Offer II 113. 课程顺序 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/1 16:25
 **/
func findOrder(numCourses int, prerequisites [][]int) []int {
	var (
		// 前置课程列表
		edges = make([][]int, numCourses)
		// 入度
		indeg  = make([]int, numCourses)
		result []int
	)

	for _, info := range prerequisites {
		edges[info[1]] = append(edges[info[1]], info[0])
		indeg[info[0]]++
	}
	// 没有前置课程的课
	q := []int{}
	for i := 0; i < numCourses; i++ {
		if indeg[i] == 0 {
			q = append(q, i)
		}
	}

	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		result = append(result, u)
		// 以u为前置课程的课
		for _, v := range edges[u] {
			indeg[v]--
			if indeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	if len(result) != numCourses {
		return []int{}
	}
	return result
}

/**
 * @Description: 剑指 Offer II 053. 二叉搜索树中的中序后继 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/1 18:43
 **/
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
	var midDfs func(node *TreeNode)
	var res *TreeNode
	var queue []*TreeNode
	midDfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		midDfs(node.Left)
		if len(queue) > 0 && queue[len(queue)-1] == p && res == nil {
			res = node
			return
		}
		queue = append(queue, node)
		midDfs(node.Right)
	}
	midDfs(root)
	return res
}

func inorderSuccessor01(root *TreeNode, p *TreeNode) *TreeNode {
	var res *TreeNode

	for root != nil {
		if root.Val > p.Val {
			res = root
			root = root.Left
		} else {
			root = root.Right
		}
	}
	return res
}
func inorderSuccessor02(root *TreeNode, p *TreeNode) *TreeNode {
	var successor *TreeNode
	if p.Right != nil {
		successor = p.Right
		for successor.Left != nil {
			successor = successor.Left
		}
		return successor
	}
	node := root
	for node != nil {
		if node.Val > p.Val {
			successor = node
			node = node.Left
		} else {
			node = node.Right
		}
	}
	return successor
}

/**
 * @Description: 剑指 Offer II 115. 重建序列 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/2 9:38
 **/
func sequenceReconstruction(nums []int, sequences [][]int) bool {
	var cnt int
	var ref = make(map[int]int)
	for i := 0; i < len(nums)-1; i++ {
		ref[nums[i]] = nums[i+1]
		cnt++
	}

	for i := 0; i < len(sequences); i++ {
		for j := 0; j < len(sequences[i])-1; j++ {
			if ref[sequences[i][j]] == sequences[i][j+1] {
				cnt--
				ref[sequences[i][j]] = -1
			}
		}
	}
	return cnt == 0
}

/**
 * @Description: 剑指 Offer II 054. 所有大于等于节点的值之和
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/8/2 9:52
 **/
func convertBST054(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	var midSearch func(node *TreeNode)
	var nums []int
	midSearch = func(node *TreeNode) {
		if node == nil {
			return
		}
		midSearch(node.Left)
		nums = append(nums, node.Val)
		midSearch(node.Right)
	}
	midSearch(root)
	// 数字：比该数字大的和
	var sumMap = make(map[int]int)
	sumMap[nums[len(nums)-1]] = nums[len(nums)-1]
	for i := len(nums) - 2; i >= 0; i-- {
		var sum = nums[i] + nums[i+1]
		sumMap[nums[i]] = sum
		nums[i] = sum
	}

	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		node.Val = sumMap[node.Val]
		dfs(node.Left)
		dfs(node.Right)
	}
	dfs(root)
	return root
}

func convertBST0541(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	var dfsRight func(node *TreeNode)
	var sum int
	dfsRight = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfsRight(node.Right)
		node.Val += sum
		sum = node.Val
		dfsRight(node.Left)
	}

	dfsRight(root)
	return root
}

/**
 * @Description: 剑指 Offer II 055. 二叉搜索树迭代器 中等
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/8/2 10:27
 **/
type BSTIterator struct {
	nodes []int
}

func Constructor055(root *TreeNode) (it BSTIterator) {
	it.inorder(root)
	return
}

func (this *BSTIterator) Next() int {
	x := this.nodes[0]
	this.nodes = this.nodes[1:]
	return x
}

func (this *BSTIterator) inorder(node *TreeNode) {
	if node == nil {
		return
	}
	this.inorder(node.Left)
	this.nodes = append(this.nodes, node.Val)
	this.inorder(node.Right)

}
func (this *BSTIterator) HasNext() bool {
	return len(this.nodes) > 0
}

/**
 * @Description: 剑指 Offer II 074. 合并区间 z中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/2 13:31
 **/
func merge074(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	var res = [][]int{{intervals[0][0], intervals[0][1]}}
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] > res[len(res)-1][1] {
			res = append(res, intervals[i])
		} else if intervals[i][1] > res[len(res)-1][1] {
			res[len(res)-1][1] = intervals[i][1]
		}
	}
	return res
}

/**
 * @Description:  剑指 Offer II 118. 多余的边 中等
 * @Keyword: 并查集
 * @Author: kami
 * @Date: 2022/8/2 15:36
 **/
func findRedundantConnection(edges [][]int) []int {
	parent := make([]int, len(edges)+1)
	for i := range parent {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(from, to int) bool {
		x, y := find(from), find(to)
		if x == y {
			return false
		}
		parent[x] = y
		return true
	}
	for _, e := range edges {
		if !union(e[0], e[1]) {
			return e
		}
	}
	return nil
}

/**
 * @Description: 剑指 Offer II 057. 值和下标之差都在给定的范围内 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/2 16:47
 **/
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
	// 10  k=3,t=5
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j <= i+k && j < len(nums); j++ {
			var diff = nums[i] - nums[j]
			if abs(diff) <= t {
				return true
			}
		}
	}
	return false
}

// 桶
func containsNearbyAlmostDuplicate01(nums []int, k int, t int) bool {
	var size = t + 1
	var bucketMap = make(map[int]int)
	for i := 0; i < len(nums); i++ {
		var idx = getBucketIdx(nums[i], size)
		if val, ok := bucketMap[idx]; ok {
			if abs(val-i) <= k {
				return true
			}
		}
		if val, ok := bucketMap[idx-1]; ok && abs(nums[val]-nums[i]) <= t && abs(val-i) <= k {
			return true
		}
		if val, ok := bucketMap[idx+1]; ok && abs(nums[val]-nums[i]) <= t && abs(val-i) <= k {
			return true
		}
		bucketMap[idx] = i
	}
	return false
}

func getBucketIdx(num, size int) int {
	if num >= 0 {
		return num / size
	}
	return (num+1)/size - 1
}

/**
 * @Description: 剑指 Offer II 111. 计算除法 中等
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/8/3 9:40
 **/
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	// 给方程组中的每个变量编号
	id := map[string]int{}
	for _, eq := range equations {
		a, b := eq[0], eq[1]
		if _, has := id[a]; !has {
			id[a] = len(id)
		}
		if _, has := id[b]; !has {
			id[b] = len(id)
		}
	}

	// 建图
	type edge struct {
		to     int
		weight float64
	}
	graph := make([][]edge, len(id))
	for i, eq := range equations {
		v, w := id[eq[0]], id[eq[1]]
		graph[v] = append(graph[v], edge{w, values[i]})
		graph[w] = append(graph[w], edge{v, 1 / values[i]})
	}

	bfs := func(start, end int) float64 {
		ratios := make([]float64, len(graph))
		ratios[start] = 1
		queue := []int{start}
		for len(queue) > 0 {
			v := queue[0]
			queue = queue[1:]
			if v == end {
				return ratios[v]
			}
			for _, e := range graph[v] {
				if w := e.to; ratios[w] == 0 {
					ratios[w] = ratios[v] * e.weight
					queue = append(queue, w)
				}
			}
		}
		return -1
	}

	ans := make([]float64, len(queries))
	for i, q := range queries {
		start, hasS := id[q[0]]
		end, hasE := id[q[1]]
		if !hasS || !hasE {
			ans[i] = -1
		} else {
			ans[i] = bfs(start, end)
		}
	}
	return ans
}
